Involuntary weight loss or wasting indicative of severe protein energy malnutrition is a frequent complication of AIDS. Since wasting associated with AIDS is characterized by a loss of muscle mass, and because the prognosis for patients with AIDS worsens with the loss of fat free mass, we hypothesize that a program of progressive resistance and aerobic exercise prescribed in combination with megestrol acetate will result in greater increases in lean body mass than either intervention alone for patients with AIDS-related weight loss.